package com.lucien.linkedList;



public class Josepfu {
    public static void main(String[] args) {
        circleSingleLinkedList list = new circleSingleLinkedList();
        list.add(10);
        list.showBoy();

        System.out.println("出圈");
        list.countBoy(1,3,10);
    }
}
//创建单向环形链表
class circleSingleLinkedList{
        //创建一个first节点，当前没有编号
        private Boy first = null;

        //添加节点，构成一个环形链表
        public void add(int nums){//传入需要添加节点的个数
            //需要先对nums做校验
            if (nums <1){
                System.out.println("nums的值不正确");
                return;
            }
            Boy curBoy = null;//辅助指针，帮助遍历循环
            //使用for循环来创建环形链表
            for (int i = 1; i <= nums; i++) {
                //根据编号，创建节点
                Boy boy = new Boy(i);
                //如果是第一个节点
                if (i == 1){
                    first = boy;
                    first.setNext(first);//构成换
                    curBoy = first;//让curBoy指向第一个节点
                }else{
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }

        //遍历环形链表
        public void showBoy(){
            //判断链表是否为空
            if (first == null){
                System.out.println("链表为空");
                return;
            }
            Boy curBoy = first;
            while (true){
                System.out.printf("节点的编号%d\n",curBoy.getNo());
                if (curBoy.getNext() == first){//已经遍历完成
                    break;
                }
                curBoy = curBoy.getNext();
            }
        }

    /**
     * 根据用户输入计算出节点出圈的顺序
     * @param startNo    表示从第几个节点开始数数
     * @param countNum   表示数几下
     * @param nums       表示最初有几个小孩在圈中
     */
        public void countBoy(int startNo,int countNum,int nums){
            if (startNo <1 || startNo > nums || first == null){
                System.out.println("输入的参数有误，请重新输入");
                return;
            }
            //创建一个辅助指针
            Boy temp = first;
            //将创建的辅助指针指向环形链表的最后
            while (true){
                if (temp.getNext() == first){//说明temp指向最后
                    break;
                }
                temp = temp.getNext();
            }
            //报数前，让first和temp指针先移动 startNo - 1次
            for (int i = 0; i < startNo - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            //报数时，让first和temp指针同时移动 countNum - 1次然后出圈，知道圈中只剩一个节点
            while (true){
                if (temp == first){//只剩一个节点
                    break;
                }
                //让first 和 temp 同时移动countNum - 1
                for (int i = 0; i < countNum - 1; i++) {
                    first = first.getNext();
                    temp = temp.getNext();
                }
                //这时first指向的节点就时要出圈的节点
                System.out.printf("节点编号%d出圈\n",first.getNo());
                //这时将first指向的节点出圈
                first = first.getNext();
                temp.setNext(first);
            }
            System.out.printf("最后留在圈中节点编号为%d\n",temp.getNo());
        }

}
//创建一个Boy类，表示一个节点
class Boy{
    private int no;//编号
    private Boy next;//指向下一个节点，默认为空

    public Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}
